#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <ctime>
#include <cstdlib>

#ifdef LINUX
#  include <cstdint>
#  define __int64 uint64_t
#endif

typedef std::vector<unsigned char>  TLongHex;

static const unsigned int   kBytesLnDigit   =   3;
static const unsigned int   kBytesInDigit   =   1 << kBytesLnDigit;
static const unsigned int   kNextDigitValue =   1 << 8;
static const unsigned int   kMaxDigitValue  =   kNextDigitValue - 1;

void toHex(const unsigned int dec, TLongHex& hex)
{
    hex.clear();
    unsigned int    value   =   dec;
    while (value != 0) {
        unsigned char   digit   =   value & kMaxDigitValue;
        value   >>=  kBytesInDigit;
        hex.push_back(digit);
    }
}

unsigned int fromHex(const TLongHex& hex)
{
    unsigned int    ret =   0;
    for ( TLongHex::const_reverse_iterator rDigitPos = hex.rbegin()
        ; rDigitPos != hex.rend()
        ; ++rDigitPos ) {
        ret <<=  kBytesInDigit;
        ret +=  *rDigitPos;
    }
    return ret;
}

bool testTransform(unsigned int dec)
{
    TLongHex    hex;
    toHex(dec, hex);
    return dec == fromHex(hex);
}

#define HEX_TEST_TRANSFORM(x) \
    if (false == testTransform(x)) { \
        std::cerr << "error on " << x << std::endl; \
        return 1; \
    }

struct TDigitResult {
public:
    TDigitResult(unsigned char nextDigit, unsigned char thisDigit)
    : NextDigit(nextDigit)
    , ThisDigit(thisDigit)
    {}

    unsigned char   NextDigit;
    unsigned char   ThisDigit;
};

static TDigitResult hexDigitMinus( const unsigned char l
                                 , const unsigned char r
                                 , const unsigned char lastDigitresult )
{
    unsigned int    from    =   l;
    unsigned int    minused =   static_cast<unsigned int>(r) + lastDigitresult;
    if (from >= minused) {
        return TDigitResult(0, from - minused);
    } else {
        return TDigitResult(1, kNextDigitValue + l - minused);
    }
}

static bool notNull(const unsigned char digit)
{
    return digit != 0;
}

void hexMinusLesser(TLongHex& from, const TLongHex& minused)
{
    TDigitResult    digitResult(0, 0);
    size_t          digitNum    =   0;
    size_t          commonSize  =   std::min(from.size(), minused.size());
    while (digitNum < commonSize) {
        digitResult     =   hexDigitMinus( from[digitNum]
                                         , minused[digitNum]
                                         , digitResult.NextDigit );
        from[digitNum]  =   digitResult.ThisDigit;
        digitNum        +=  1;
    }

    while ((digitResult.NextDigit != 0) && (digitNum < from.size())) {
        digitResult     =   hexDigitMinus( from[digitNum]
                                         , 0
                                         , digitResult.NextDigit );
        from[digitNum]  =   digitResult.ThisDigit;
        digitNum        +=  1;
    }

    TLongHex::iterator  rNotNull    =   std::find_if( from.rbegin()
                                                    , from.rend()
                                                    , notNull ).base();
    from.erase(rNotNull, from.end());
}

bool testMinus(const unsigned int l, const unsigned int r)
{
    unsigned int    max =   std::max(l, r);
    unsigned int    min =   std::min(l, r);

    TLongHex    maxHex;
    TLongHex    minHex;

    toHex(max, maxHex);
    toHex(min, minHex);

    hexMinusLesser(maxHex, minHex);

    return (max - min) == fromHex(maxHex);
}

#define HEX_TEST_MINUS(x, y) \
    if (false == testMinus(x, y)) { \
        std::cerr << "error on " << x << " - " << y << std::endl; \
        return 1; \
    }

bool isHexLess(const TLongHex& l, const TLongHex& r)
{
    if (l.size() < r.size()) {
        return true;
    }

    if (l.size() > r.size()) {
        return false;
    }

    if (0 == l.size()) {
        return false;
    }

    bool        isEqual =   true;
    long int    idx     =   l.size() - 1;

    while ((idx >= 0) && (true == isEqual)) {
        isEqual =   l[idx] == r[idx];
        idx     -=  1;
    }

    if (true == isEqual) {
        return false;
    }

    return l[idx + 1] < r[idx + 1];
}

bool isHexEqual(const TLongHex& r, const TLongHex& l)
{
    return ((false == isHexLess(r, l)) && (false == isHexLess(l, r)));
}

bool testLess(const unsigned int l, const unsigned int r)
{
    TLongHex    lHex;
    TLongHex    rHex;
    toHex(l, lHex);
    toHex(r, rHex);
    return (l < r) == isHexLess(lHex, rHex);
}

#define HEX_TEST_LESS(x, y) \
    if (false == testLess(x, y)) { \
        std::cerr << "error on " << x << " < " << y << std::endl; \
        return 1; \
    }

static TDigitResult makeDigitResult(const unsigned int dec)
{
    return TDigitResult(dec >> kBytesInDigit, dec & kMaxDigitValue);
}

static TDigitResult hexDigitMultiply( const unsigned char target
                                    , const unsigned int  pow
                                    , const unsigned char lastDigitresult )
{
    unsigned int    result  =   (static_cast<unsigned int>(target) << pow) + lastDigitresult;
    return makeDigitResult(result);
}

void multiplyByPow2Less8( const TLongHex&    target
                        , const unsigned int pow
                        , TLongHex&          result)
{
    result.assign(target.size(), 0);
    TDigitResult    lastDigitResult(0,0);
    for (unsigned int digitIdx = 0; digitIdx != target.size(); ++digitIdx) {
        lastDigitResult     =   hexDigitMultiply( target[digitIdx]
                                                , pow
                                                , lastDigitResult.NextDigit );
        result[digitIdx]    =   lastDigitResult.ThisDigit;
    }

    if (0 != lastDigitResult.NextDigit) {
        result.push_back(lastDigitResult.NextDigit);
    }
}

bool testMultiplyByPow2Less8(const unsigned int target, const unsigned int pow)
{
    unsigned int    checkedPow  =   pow & (kBytesInDigit - 1);
    TLongHex        targetHex;
    TLongHex        result;
    toHex(target, targetHex);
    multiplyByPow2Less8(targetHex, checkedPow, result);

    return ((target << checkedPow) == fromHex(result));
}

#define HEX_TEST_MULTIPLY_L8(x, y) \
    if (false == testMultiplyByPow2Less8(x, y)) { \
        std::cerr << "error on " << x << " * 2 ^ " << y << std::endl; \
        return 1; \
    }

void multiplyByPow2Of8(TLongHex& target, const unsigned int pow)
{
    unsigned int    decreasedPow    =   pow >> kBytesLnDigit;
    target.insert(target.begin(), decreasedPow, 0);
}

bool testMultiplyByPow2Of8(const unsigned int target, const unsigned int pow)
{
    unsigned int    checkedPow  =   (pow >> kBytesLnDigit) << kBytesLnDigit;
    TLongHex        targetHex;
    toHex(target, targetHex);
    multiplyByPow2Of8(targetHex, checkedPow);

    return ((target << checkedPow) == fromHex(targetHex));
}

#define HEX_TEST_MULTIPLY_8(x, y) \
    if (false == testMultiplyByPow2Less8(x, y)) { \
        std::cerr << "error on " << x << " * 2 ^ " << y << std::endl; \
        return 1; \
    }

void multiplyByPow2( const TLongHex&    target
                   , const unsigned int pow
                   , TLongHex&          result )
{
    unsigned int    powOf8      =   (pow >> kBytesLnDigit) << kBytesLnDigit;
    unsigned int    powLess8    =   pow & (kBytesInDigit - 1);
    multiplyByPow2Less8(target, powLess8, result);
    multiplyByPow2Of8(result, powOf8);
}

bool testMultiplyByPow2(const unsigned int target, const unsigned int pow)
{
    TLongHex        targetHex;
    TLongHex        result;
    toHex(target, targetHex);
    multiplyByPow2(targetHex, pow, result);

    return ((target << pow) == fromHex(result));
}

#define HEX_TEST_MULTIPLY(x, y) \
    if (false == testMultiplyByPow2(x, y)) { \
        std::cerr << "error on " << x << " * 2 ^ " << y << std::endl; \
        return 1; \
    }

unsigned int msb(const TLongHex& x)
{
    unsigned char   last(x.back());
    unsigned char   divider =   0;
    while (last > 0) {
        last    >>= 1;
        divider +=  1;
    }

    return divider;
}

void MBNDivide( const TLongHex& numerator
              , const TLongHex& denumerator
              , TLongHex&       quotient
              , TLongHex&       remainder )
{
    if (denumerator.empty()) {
        return;
    }

    remainder.assign(numerator.begin(), numerator.end());
    quotient.clear();

    TLongHex    candidate;
    TLongHex    nextCandidate;
    while (false == isHexLess(remainder, denumerator)) {

        unsigned int    powOf2  =   ((remainder.size() - denumerator.size()) << kBytesLnDigit)
                                  + (static_cast<int>(msb(remainder)) - msb(denumerator));

        if (0 != powOf2) {
            powOf2  -=  1;
        }

        multiplyByPow2(denumerator, powOf2, candidate);
        multiplyByPow2Less8(candidate, 1, nextCandidate);

        unsigned int    addition    =   0;
        const TLongHex* mostHex     =   &candidate;

        if (  (true == isHexLess(nextCandidate, remainder))
           || (true == isHexEqual(nextCandidate, remainder)) ) {
            addition    =   1;
            mostHex     =   &nextCandidate;
        }

        hexMinusLesser(remainder, *mostHex);
        powOf2  +=  addition;

        unsigned int    digitNum    =   powOf2 >> kBytesLnDigit;
        if (quotient.size() <= digitNum) {
            quotient.resize(digitNum + 1, 0);
        }
        unsigned int    place       =   powOf2 & (kBytesInDigit - 1);
        quotient[digitNum]  |=  static_cast<unsigned char>(1) << place;
    }
}

bool testDivide(const unsigned int numerator, const unsigned int denumerator)
{
    TLongHex        numeratorHex;
    TLongHex        denumeratorHex;
    TLongHex        quotinentHex;
    TLongHex        reminderHex;

    toHex(numerator, numeratorHex);
    toHex(denumerator, denumeratorHex);

    MBNDivide(numeratorHex, denumeratorHex, quotinentHex, reminderHex);

    return (  ((numerator / denumerator) == fromHex(quotinentHex))
           && ((numerator % denumerator) == fromHex(reminderHex)) );
}

#define HEX_TEST_DIVIDE(x, y) \
    if (false == testDivide(x, y)) { \
        std::cerr << "error on " << x << " / " << y << std::endl; \
        return 1; \
    }

unsigned int getRandom()
{
    return rand() % std::numeric_limits<unsigned int>::max() + 1;
}

std::vector<unsigned char> ll2vc(__int64 x)
{
    unsigned char* c = (unsigned char*)&x;
    std::vector<unsigned char> res; res.resize(8);
    int i;
    for (i = 0; i < 8; i++)
        res[i] = c[i];
    for (i = 7; i >= 0 && !res[i]; i--);
    res.resize(i + 1);
    return res;
}

__int64 vc2ll(const std::vector<unsigned char>& x)
{
    __int64 res = 0;
    for (auto it = x.rbegin(); it != x.rend(); it++)
        res = (res << 8) + (unsigned char)*it;
    return res;
}

bool test4(__int64 a1, __int64 a2)
{
    std::vector<unsigned char> v1 = ll2vc(a1), v2 = ll2vc(a2), vq, vr;
    MBNDivide(v1, v2, vq, vr);
    __int64 q = vc2ll(vq), r = vc2ll(vr);
    bool b = q == a1 / a2 && r == a1 % a2;
    return b;
}

int main(int argC, char** argV)
{
    srand(time(NULL));

    HEX_TEST_TRANSFORM(1000);
    HEX_TEST_TRANSFORM(11);
    HEX_TEST_TRANSFORM(256);

    HEX_TEST_MINUS(257, 256);
    HEX_TEST_MINUS(3000, 3000);
    HEX_TEST_MINUS(100, 10);
    HEX_TEST_MINUS(3000, 100);
    HEX_TEST_MINUS(3000, 258);

    HEX_TEST_LESS(256, 320);
    HEX_TEST_LESS(320, 256);
    HEX_TEST_LESS(257, 256);
    HEX_TEST_LESS(256, 256);
    HEX_TEST_LESS(257, 256);
    HEX_TEST_LESS(100, 10);
    HEX_TEST_LESS(10, 100);
    HEX_TEST_LESS(3000, 100);
    HEX_TEST_LESS(100, 3000);

    HEX_TEST_MULTIPLY_L8(256, 1);
    HEX_TEST_MULTIPLY_L8(255, 7);
    HEX_TEST_MULTIPLY_L8(311, 2);
    HEX_TEST_MULTIPLY_L8(415, 6);

    HEX_TEST_MULTIPLY_8(256, 8);
    HEX_TEST_MULTIPLY_8(255, 16);
    HEX_TEST_MULTIPLY_8(311, 32);
    HEX_TEST_MULTIPLY_8(415, 64);

    HEX_TEST_MULTIPLY(256, 10);
    HEX_TEST_MULTIPLY(255, 15);
    HEX_TEST_MULTIPLY(311, 9);
    HEX_TEST_MULTIPLY(415, 17);
    HEX_TEST_MULTIPLY(415, 0);

    HEX_TEST_DIVIDE(8, 1)
    HEX_TEST_DIVIDE(104, 1)
    HEX_TEST_DIVIDE(1150, 1)
    HEX_TEST_DIVIDE(12656, 1)
    HEX_TEST_DIVIDE(139224, 1)
    HEX_TEST_DIVIDE(974568, 1)
    HEX_TEST_DIVIDE(4872844, 1)
    HEX_TEST_DIVIDE(14618532, 1)
    HEX_TEST_DIVIDE(43855598, 1)
    HEX_TEST_DIVIDE(256, 10);
    HEX_TEST_DIVIDE(123234124, 243);
    HEX_TEST_DIVIDE(32822, 256);
    HEX_TEST_DIVIDE(10, 256);
    HEX_TEST_DIVIDE(255, 15);
    HEX_TEST_DIVIDE(311, 9);
    HEX_TEST_DIVIDE(415, 17);

    for (unsigned int times = 0; times != 1000000; ++times) {
        HEX_TEST_DIVIDE(getRandom(), getRandom());
    }

    for (int i = 0; i < 100000; i++)
    {
        __int64 a1 = rand() * rand(), a2 = rand() + 1;
        if (!test4(a1, a2))
        {
            std::cerr << a1 << "/" << a2 << std::endl;
        }
    }

    return 0;
}
